package com.atwy.tree;

/**
 * 顺序存储二叉树
 * 使用数组存储二叉树，只适用于完全二叉树。
 * 因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
 * 普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。
 * <p>
 * 完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。
 * <p>
 * 完全二叉树具有这样的性质：
 * 将树中节点按照层次并从左到右依次标号（1,2,3,...），
 * 若节点 i 有左右孩子，则其左孩子节点为 2*i，右孩子节点为 2*i+1
 * <p>
 * 数组下标是从0开始的，所以节点i的下标 index = i-1。如果是下标的话，树结构应该是
 *       0
 *  1        2
 * 3 4      5 6
 * <p>
 * 可以发现index的节点，左孩子节点下标是 2*index+1, 右孩子节点下标是 2*index+2 。
 * <p>
 * 按节点的数学关系来看，i = index + 1,左孩 = 2*(index+1),右孩=2*(index+1)+1,而我们用数组下标来看的话
 * 左孩下标 = 2*(index+1)-1 = 2*index+1 ,右孩下标 = 2*(index+1)+1 = 2*index+2 。
 * <p>
 * 在堆排序时会用到
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        // 创建一个顺序二叉树
        ArrBinaryTree tree = new ArrBinaryTree(array);

        System.out.println("前序遍历：");
        tree.preOrder();// 1 2 4 5 3 6 7

        System.out.println("中序遍历：");
        tree.middleOrder();// 4 2 5 1 6 3 7

        System.out.println("后序遍历：");
        tree.postOrder();// 4 5 2 6 7 3 1

    }
}

class ArrBinaryTree {
    private int[] array;

    public ArrBinaryTree(int[] array) {
        this.array = array;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        this.preOrder(0);
        System.out.println();
    }

    /**
     * 重载前序遍历
     *
     * @param index
     */
    private void preOrder(int index) {
        if (array == null || array.length == 0) {
            System.out.println("为空，不能遍历~");
            return;
        }
        // 输出当前元素
        System.out.print(array[index]);

        // 左递归遍历
        if (2 * index + 1 < array.length) {
            // 左孩下标
            this.preOrder(2 * index + 1);
        }
        if (2 * index + 2 < array.length) {
            this.preOrder(2 * index + 2);
        }
    }

    /**
     * 中序遍历
     */
    public void middleOrder() {
        this.middleOrder(0);
        System.out.println();
    }

    private void middleOrder(int index) {
        if (array == null || array.length == 0) {
            System.out.println("为空，不能遍历~");
            return;
        }

        // 左递归遍历
        if (2 * index + 1 < array.length) {
            // 左孩下标
            this.middleOrder(2 * index + 1);
        }
        // 输出当前元素
        System.out.print(array[index]);

        if (2 * index + 2 < array.length) {
            this.middleOrder(2 * index + 2);
        }
    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        this.postOrder(0);
        System.out.println();
    }

    private void postOrder(int index) {
        if (array == null || array.length == 0) {
            System.out.println("为空，不能遍历~");
            return;
        }

        // 左递归遍历
        if (2 * index + 1 < array.length) {
            // 左孩下标
            this.postOrder(2 * index + 1);
        }

        if (2 * index + 2 < array.length) {
            this.postOrder(2 * index + 2);
        }
        // 输出当前元素
        System.out.print(array[index]);
    }
}
